1. Field of the Invention
The present invention relates to a scheduling method of a switch and, more particularly, to a stepwise QoS scheduling method in output-buffered switches for broadband networks.
2. Description of Related Art
Broadband networking technology enables the development and deployment of distributed multicast and multimedia applications combining various types of media data, such as text, video, and voice. These broadband applications often require different grades of Quality-of-Service (QoS) requirements, such as delay, jitter, and throughput. To meet these requirements, particularly for output-buffered switches, research emphasis has been placed on the design of scalable schedulers that assure fairness and QoS performance despite ever-increasing magnitude of supported flows.
Recently proposed QoS scheduling algorithms for output-buffered switches advocate the computation and maintenance of a priority queue, according to deadlines, virtual finishing times, or other time stamps that are associated with packets. For example, the packet-by-packet generalized processor sharing (PGPS) algorithm has been proposed as a packet emulation of the ideal bit-by-bit round-robin discipline. At each packet arrival, PGPS computes a timestamp that corresponds to the packet departing time, according to the number of backlogged flows in the system at that instant. Packets are then transmitted in increasing order of their timestamps. A major limitation of PGPS is significant computational complexity O(N), increasing linearly with the number of concurrent flows N.
To reduce computational overhead, much effort has been made on the simplification of the task of priority-queue maintenance. Promising algorithms include Worst-case Fair Weighted Fair Queueing (WF2Q), Self-Clocked Fair Queueing (SCFQ), and Frame-based Fair Queueing (FFQ). In WF2Q, the next packet to serve is selected from a smaller set of packets having already started receiving service in the corresponding GPS system. It offers improved worst-case fairness, but still incurs high computational overhead. SCFQ proposed a simpler approximate computation of timestamps, however resulting in an increase in delay bound and poorer worst-case fairness. Based on a general framework of rate-proportional servers, FFQ adopted a framing mechanism to keep track the amount of normalized service actually received and missed only periodically for simpler timestamp computation. It was shown that the discipline exhibits constant asymptotic computational complexity but undergoes lower grade of worst-case fairness. Another significant limitation is the imposed constraint that the frame size has to exceed the sum of the maximum packet sizes of all flows. As a whole, all above algorithms advocate either static or coarse-grained simplification of timestamp computation, resulting in unnecessary performance downgrade under normal flow intensity. Therefore, it is desirable to provide an improved scheduling method to mitigate and/or obviate the aforementioned problems.